﻿/**	vec_multiset.hpp
 *	----	Create Time Stamp	--2009-03-09 01:49:02--
 *------------------------------------------------------------------------------
 *	Mean	:
 *	Author	:Nick Shallery	(nicknide@gmail.com)
 *	Version	:1.0.3.11	(2009-07-14 23:44:47)
 *------------------------------------------------------------------------------
**/	/*YOU HAVE ALL LEFT WITH THIS CODE WHILE YOU KEEP COMMENT IN EVERY COPY.*/

#if			!defined(__LOLIX__TOY__VEC_SET__NICK__K_IN_G__)
#define		__LOLIX__TOY__VEC_SET__NICK__K_IN_G__
//==============================================================================
//--------------------------------------------------------------------------


#if			!defined(__LOLIX__LOLI_X_CFG__K_IN_G__)
	#include	"../lolix_cfg.h"
#endif	//	!defined(__LOLIX__LOLI_X_CFG__K_IN_G__)

#if			!defined(__LOLIX__LOLIX_TYPE__K_IN_G__)
	#include	"../lolix_type.h"
#endif	//	!defined(__LOLIX__LOLIX_TYPE__K_IN_G__)

#if			!defined(__LOLIX_TOY__STD_ALGORITHM__NICK__K_IN_G__)
	#include	"./std_algorithm.hpp"
#endif	//	!defined(__LOLIX__TOY__STD_ALGORITHM__NICK__K_IN_G__)

#if			!defined(__LOLIX__TOY__STD_VECTOR__NICK__K_IN_G__)
	#include	"./std_vector.hpp"
#endif	//	!defined(__LOLIX__TOY__STD_VECTOR__NICK__K_IN_G__)

#if			!defined(__LOLIX__TOY__PAIR_TYPE__K_IN_G__)
	#include	"./pair_type.hpp"
#endif	//	!defined(__LOLIX__TOY__PAIR_TYPE__K_IN_G__)


//#if			LOLIX_CFG__IS_DEBUG
//	#define		__LOLIX_TMP__DEFINE__CHECK_VALID(v)	__check_valid(v)
//#else	//	LOLIX_CFG__IS_DEBUG
//	#define		__LOLIX_TMP__DEFINE__CHECK_VALID(v)
//#endif	//	LOLIX_CFG__IS_DEBUG


namespace lolix{namespace toy{


template<typename _TVal, typename _TLess = lolix::toy::less, typename _TAlc = lolix::toy::allocator<void> >
class vec_multiset
	: private vector<_TVal, _TAlc>
{
	typedef	vec_multiset<_TVal, _TLess, _TAlc>		this_type;
	typedef	vector<_TVal, _TAlc>					base_type;
protected:
	typedef	typename type::type_choise<type::type_equal<_TLess, void>::value, less, _TLess>::type	_T_LessType;
	_T_LessType	_less_cmp;

public:
	typedef	_T_LessType								less_type;
	typedef	typename	base_type::allocator_type	allocator_type;
	typedef typename	base_type::size_type		size_type;
	typedef typename	base_type::difference_type	difference_type;
	typedef typename	base_type::pointer			pointer;
	typedef typename	base_type::const_pointer	const_pointer;
	typedef typename	base_type::reference		reference;
	typedef typename	base_type::const_reference	const_reference;
	typedef typename	base_type::value_type		value_type;
	typedef	typename	base_type::const_iterator	const_iterator;
	typedef	typename	base_type::iterator			iterator;
	typedef	typename	base_type::reverse_iterator	reverse_iterator;
	typedef	typename	base_type::const_reverse_iterator	const_reverse_iterator;
	typedef	value_type	key_type;
	typedef	typename	type::pass_type<value_type>::const_value_type	const_pass_type;

	using base_type::begin;
	using base_type::end;
	using base_type::rbegin;
	using base_type::rend;
	using base_type::get_allocator;

	LOLIX_INLINE_CALL vec_multiset<_TVal, _TLess, _TAlc>(void)
		: base_type()
	{ }

	LOLIX_INLINE_CALL vec_multiset<_TVal, _TLess, _TAlc>(_TAlc const& alc)
		: base_type(alc)
	{ }


	LOLIX_INLINE_CALL iterator find(key_type const& key)
		{
		iterator iter = lolix::toy::lower_bound(begin(), end(), key, _less_cmp);
		if ( iter != end() && *iter == key )
			return iter;
		return end();
		}

	LOLIX_INLINE_CALL const_iterator find(key_type const& key)const
		{
		return const_cast<this_type*>(this)->find(key);
		}

	LOLIX_INLINE_CALL size_type count(const_pass_type val)const
		{
		return upper_bound(val) - lower_bound(val);
		}

	using base_type::capacity;
	using base_type::clear;
	using base_type::reserve;
	using base_type::empty;
	using base_type::size;
	LOLIX_INLINE_CALL pair<iterator, bool> insert(const_pass_type val)
		{
		iterator iter = lower_bound(begin(), end(), key, _less_cmp);
		return pair<iterator, bool>(base_type::insert(iter, val), true);
		}

	using base_type::erase;
	LOLIX_INLINE_CALL iterator erase(const_pass_type val)
		{
			iterator bg = begin(), ed = end();
			return base_type::erase(
				lower_bound(bg, ed, val, _less_cmp)
				, upper_bound(bg, ed, val, _less_cmp)
				);
		}

	LOLIX_INLINE_CALL lolix::toy::pair<const_iterator, const_iterator> equal_range(const_pass_type val)const
		{
		return lolix::toy::pair<const_iterator, const_iterator>(lower_bound(val), upper_bound(val));
		}

	LOLIX_INLINE_CALL lolix::toy::pair<iterator, iterator> equal_range(const_pass_type val)
		{
		return lolix::toy::pair<iterator, iterator>(lower_bound(val), upper_bound(val));
		}

	LOLIX_INLINE_CALL iterator lower_bound(const_pass_type val)
		{
		iterator bg = begin(), ed = end();
		return lower_bound(bg, ed, val, _less_cmp);
		}

	LOLIX_INLINE_CALL const_iterator lower_bound(const_pass_type val)const
		{
		const_iterator bg = begin(), ed = end();
		return lower_bound(bg, ed, val, _less_cmp);
		}

	LOLIX_INLINE_CALL iterator upper_bound(const_pass_type val)
		{
		iterator bg = begin(), ed = end();
		return upper_bound(bg, ed, val, _less_cmp);
		}

	LOLIX_INLINE_CALL const_iterator upper_bound(const_pass_type val)const
		{
		const_iterator bg = begin(), ed = end();
		return upper_bound(bg, ed, val, _less_cmp);
		}

	LOLIX_INLINE_CALL void swap(this_type& o)
		{
		base_type::swap((base_type&)o);
		}

	using base_type::operator [];
protected:
	LOLIX_INLINE_CALL iterator __Insert(iterator iter, const_pass_type val)
		{
		return base_type::insert(iter, val);
		}
};



template<typename _TVal, typename _TLess = lolix::toy::less, typename _TAlc = lolix::toy::allocator<void> >
class vec_set
	: private vec_multiset<_TVal, _TLess, _TAlc>
{
	typedef	vec_set<_TVal, _TLess, _TAlc>			this_type;
	typedef	vec_multiset<_TVal, _TLess, _TAlc>		base_type;

public:
	typedef	typename	base_type::less_type		less_type;
	typedef	typename	base_type::allocator_type	allocator_type;
	typedef typename	base_type::size_type		size_type;
	typedef typename	base_type::difference_type	difference_type;
	typedef typename	base_type::pointer			pointer;
	typedef typename	base_type::const_pointer	const_pointer;
	typedef typename	base_type::reference		reference;
	typedef typename	base_type::const_reference	const_reference;
	typedef typename	base_type::value_type		value_type;
	typedef	typename	base_type::const_iterator	const_iterator;
	typedef	typename	base_type::iterator			iterator;
	typedef	typename	base_type::reverse_iterator	reverse_iterator;
	typedef	typename	base_type::const_reverse_iterator	const_reverse_iterator;
	typedef	value_type	key_type;

	using base_type::begin;
	using base_type::end;
	using base_type::rbegin;
	using base_type::rend;
	using base_type::get_allocator;

	LOLIX_INLINE_CALL vec_set<_TVal, _TLess, _TAlc>(void)
		: base_type()
	{ }

	LOLIX_INLINE_CALL vec_set<_TVal, _TLess, _TAlc>(_TAlc const& alc)
		: base_type(alc)
	{ }

	LOLIX_INLINE_CALL size_type count(const_pass_type val)const
		{
		const_iterator iter = lower_bound(val);
		if ( iter == end() || iter != val )
			return 0;
		return 1;
		}

	using base_type::find;
	using base_type::capacity;
	using base_type::clear;
	using base_type::reserve;
	using base_type::empty;
	using base_type::size;
	LOLIX_INLINE_CALL pair<iterator, bool> insert(const_pass_type val)
		{
		iterator iter = lolix::toy::lower_bound(begin(), end(), val, _less_cmp);
		if ( iter != end() && *iter == val )
			return pair<iterator, bool>(iterator(), false);
		return pair<iterator, bool>(base_type::__Insert(iter, val), true);
		}

	using base_type::erase;
	LOLIX_INLINE_CALL iterator erase(const_pass_type val)
		{
			return base_type::erase(find(val));
		}

	LOLIX_INLINE_CALL lolix::toy::pair<const_iterator, const_iterator> equal_range(const_pass_type val)const
		{
		const_iterator it = lower_bound(val);
		const_iterator ite(it);
		if ( ite != end() )
			++ite;
		return lolix::toy::pair<const_iterator, const_iterator>(it, ite);
		}

	LOLIX_INLINE_CALL lolix::toy::pair<iterator, iterator> equal_range(const_pass_type val)
		{
		iterator it = lower_bound(val);
		iterator ite(it);
		if ( ite != end() )
			++ite;
		return lolix::toy::pair<iterator, iterator>(it, ite);
		}

	using base_type::lower_bound;
	using base_type::upper_bound;

	LOLIX_INLINE_CALL void swap(this_type& o)
		{
		base_type::swap((base_type&)o);
		}

	using base_type::operator [];
};

}}

namespace lolix{
	template<typename _Ty, typename _TLess, typename _TAlc>
	LOLIX_INLINE_CALL void swap(toy::vec_multiset<_Ty, _TLess, _TAlc>& tl, toy::vec_multiset<_Ty, _TLess, _TAlc>& tr)
	{ tl.swap(tr); }
	template<typename _Ty, typename _TLess, typename _TAlc>
	LOLIX_INLINE_CALL void swap(toy::vec_set<_Ty, _TLess, _TAlc>& tl, toy::vec_set<_Ty, _TLess, _TAlc>& tr)
	{ tl.swap(tr); }
}

//--------------------------------------------------------------------------
//==============================================================================
#endif	//	!defined(__LOLIX__TOY__VEC_SET__NICK__K_IN_G__)
